{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n哈希表： 键值对(k, v)\\n\\n用list实现哈希表\\n\\ncopy               O(n)\\nget                O(1)\\nset                O(1)\\ndel                O(1)\\ncontains           O(1)\\niterator           O(n)\\n\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''\n",
    "哈希表： 键值对(k, v)\n",
    "\n",
    "用list实现哈希表\n",
    "\n",
    "copy               O(n)\n",
    "get                O(1)\n",
    "set                O(1)\n",
    "del                O(1)\n",
    "contains           O(1)\n",
    "iterator           O(n)\n",
    "\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\" \\n哈希表实现 \\n\\n在Python中，字典是通过哈希表实现的。也就是说，字典是一个数组，而数组的索引是键经过哈希函数处理后得到的。\\nkey = > hash值 => key所在的索引\\nget(key)是 O(1)\\n\\n    数据添加：把key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。\\n    数据查询：再次使用哈希函数将key转换为对应的数组下标，并定位到数组的位置获取value。\\n\\n哈希函数的目的是使键均匀地分布在数组中。由于不同的键可能具有相同的哈希值，即可能出现冲突，高级的哈希函数能够使冲突数目最小化。\\nPython中并不包含这样高级的哈希函数，几个重要（用于处理字符串和整数）的哈希函数通常情况下均是常规的类型。\\n冲突指不同键经过哈希函数计算得到相同的索引，这样造成索引重复的冲突。\\n\\npython内部采用 开放地址法 解决冲突问题。\\n    所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，\\n    那么不断通过探测函数往下找，直到找个一个空槽slot来存放待插入元素。\\n\\ntypedef struct {\\n     Py_ssize_t me_hash; \\n     PyObject *me_key;\\n     PyObject *me_value;\\n} PyDictEntry;\\n\\nme_hash用于缓存me_key的哈希值，防止每次查询时都要计算哈希值，entry有三种状态。\\n1.Unused：未使用\\n2.Active：插入元素\\n3.Dummy：删除元素时Active状态刻转换成Dummy状态。Dummy状态的元素可以在插入元素的时候将它变成Active状态，但它不可能再变成Unused状态。\\n\\n为什么entry有Dummy状态呢？这是因为采用开放寻址法中，遇到哈希冲突时会找到下一个合适的位置，例如某元素经过哈希计算应该插入到A处，\\n但是此时A处有元素的，通过探测函数计算得到下一个位置B，仍然有元素，直到找到位置C为止，此时ABC构成了探测链，查找元素时如果hash值相同，\\n那么也是顺着这条探测链不断往后找，当删除探测链中的某个元素时，比如B，如果直接把B从哈希表中移除，即变成Unused状态，\\n那么C就不可能再找到了，因为AC之间出现了断裂的现象，正是如此才出现了第三种状态---Dummy，Dummy是一种类似的伪删除方式，保证探测链的连续性。\\n\\ntypedef struct _dictobject PyDictObject;\\nstruct _dictobject {\\n    PyObject_HEAD\\n    Py_ssize_t ma_fill;  /* # Active + # Dummy */\\n    Py_ssize_t ma_used;  /* # Active */\\n\\n    /* The table contains ma_mask + 1 slots, and that's a power of 2.\\n     * We store the mask instead of the size because the mask is more\\n     * frequently needed.\\n     */\\n    Py_ssize_t ma_mask;\\n\\n    /* ma_table points to ma_smalltable for small tables, else to\\n     * additional malloc'ed memory.  ma_table is never NULL!  This rule\\n     * saves repeated runtime null-tests in the workhorse getitem and\\n     * setitem calls.\\n     */\\n    PyDictEntry *ma_table;\\n    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);\\n    PyDictEntry ma_smalltable[PyDict_MINSIZE];\\n};\\n\\n    ma_fill ：所有处于Active以及Dummy的元素个数\\n    ma_used ：所有处于Active状态的元素个数\\n    ma_mask ：所有entry的元素个数（Active+Dummy+Unused）\\n    ma_smalltable：创建字典对象时，一定会创建一个大小为PyDict_MINSIZE==8的PyDictEntry数组。默认的slot。\\n    ma_table：当entry数量小于PyDict_MINSIZE，ma_table指向ma_smalltable的首地址，当entry数量大于8时，\\n              Python把它当做一个大字典来处理，此刻会申请额外的内存空间，同时将ma_table指向这块空间。\\n              初始指向ma_smalltable，如果后期扩容，则指向新的slot空间。\\n              \\n    ma_lookup：字典元素的搜索策略\\n    \\n    PyDictObject使用PyObject_HEAD而不是PyObject_Var_HEAD，虽然字典也是变长对象，\\n    但此处并不是通过ob_size来存储字典中元素的长度，而是通过ma_used字段。\\n\\n\""
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\" \n",
    "哈希表实现 \n",
    "\n",
    "在Python中，字典是通过哈希表实现的。也就是说，字典是一个数组，而数组的索引是键经过哈希函数处理后得到的。\n",
    "key = > hash值 => key所在的索引\n",
    "get(key)是 O(1)\n",
    "\n",
    "    数据添加：把key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。\n",
    "    数据查询：再次使用哈希函数将key转换为对应的数组下标，并定位到数组的位置获取value。\n",
    "\n",
    "哈希函数的目的是使键均匀地分布在数组中。由于不同的键可能具有相同的哈希值，即可能出现冲突，高级的哈希函数能够使冲突数目最小化。\n",
    "Python中并不包含这样高级的哈希函数，几个重要（用于处理字符串和整数）的哈希函数通常情况下均是常规的类型。\n",
    "冲突指不同键经过哈希函数计算得到相同的索引，这样造成索引重复的冲突。\n",
    "\n",
    "python内部采用 开放地址法 解决冲突问题。\n",
    "    所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，\n",
    "    那么不断通过探测函数往下找，直到找个一个空槽slot来存放待插入元素。\n",
    "\n",
    "typedef struct {\n",
    "     Py_ssize_t me_hash; \n",
    "     PyObject *me_key;\n",
    "     PyObject *me_value;\n",
    "} PyDictEntry;\n",
    "\n",
    "me_hash用于缓存me_key的哈希值，防止每次查询时都要计算哈希值，entry有三种状态。\n",
    "1.Unused：未使用\n",
    "2.Active：插入元素\n",
    "3.Dummy：删除元素时Active状态刻转换成Dummy状态。Dummy状态的元素可以在插入元素的时候将它变成Active状态，但它不可能再变成Unused状态。\n",
    "\n",
    "为什么entry有Dummy状态呢？这是因为采用开放寻址法中，遇到哈希冲突时会找到下一个合适的位置，例如某元素经过哈希计算应该插入到A处，\n",
    "但是此时A处有元素的，通过探测函数计算得到下一个位置B，仍然有元素，直到找到位置C为止，此时ABC构成了探测链，查找元素时如果hash值相同，\n",
    "那么也是顺着这条探测链不断往后找，当删除探测链中的某个元素时，比如B，如果直接把B从哈希表中移除，即变成Unused状态，\n",
    "那么C就不可能再找到了，因为AC之间出现了断裂的现象，正是如此才出现了第三种状态---Dummy，Dummy是一种类似的伪删除方式，保证探测链的连续性。\n",
    "\n",
    "typedef struct _dictobject PyDictObject;\n",
    "struct _dictobject {\n",
    "    PyObject_HEAD\n",
    "    Py_ssize_t ma_fill;  /* # Active + # Dummy */\n",
    "    Py_ssize_t ma_used;  /* # Active */\n",
    "\n",
    "    /* The table contains ma_mask + 1 slots, and that's a power of 2.\n",
    "     * We store the mask instead of the size because the mask is more\n",
    "     * frequently needed.\n",
    "     */\n",
    "    Py_ssize_t ma_mask;\n",
    "\n",
    "    /* ma_table points to ma_smalltable for small tables, else to\n",
    "     * additional malloc'ed memory.  ma_table is never NULL!  This rule\n",
    "     * saves repeated runtime null-tests in the workhorse getitem and\n",
    "     * setitem calls.\n",
    "     */\n",
    "    PyDictEntry *ma_table;\n",
    "    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);\n",
    "    PyDictEntry ma_smalltable[PyDict_MINSIZE];\n",
    "};\n",
    "\n",
    "    ma_fill ：所有处于Active以及Dummy的元素个数\n",
    "    ma_used ：所有处于Active状态的元素个数\n",
    "    ma_mask ：所有entry的元素个数（Active+Dummy+Unused）\n",
    "    ma_smalltable：创建字典对象时，一定会创建一个大小为PyDict_MINSIZE==8的PyDictEntry数组。默认的slot。\n",
    "    ma_table：当entry数量小于PyDict_MINSIZE，ma_table指向ma_smalltable的首地址，当entry数量大于8时，\n",
    "              Python把它当做一个大字典来处理，此刻会申请额外的内存空间，同时将ma_table指向这块空间。\n",
    "              初始指向ma_smalltable，如果后期扩容，则指向新的slot空间。\n",
    "              \n",
    "    ma_lookup：字典元素的搜索策略\n",
    "    \n",
    "    PyDictObject使用PyObject_HEAD而不是PyObject_Var_HEAD，虽然字典也是变长对象，\n",
    "    但此处并不是通过ob_size来存储字典中元素的长度，而是通过ma_used字段。\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
